Nonvolatile data storage devices, such as embedded memory devices and removable memory devices, enable portability of data and software applications. In certain flash memory devices, multi-level cell (MLC) storage elements may each store a threshold voltage representing multiple bits of data, enhancing data storage density as compared to single-level cell (SLC) flash memory devices. The enhanced storage density may be associated with increased data errors, such as bit corruption.
To correct data errors, a flash memory device may utilize an error correcting code (ECC) technique. For example, the flash memory device may encode user data using an ECC technique to generate encoded data, such as an ECC codeword. The encoded data may be stored at the flash memory device and may be decoded by a decoder of the flash memory device, such as in response to a request for read access to the data from a host device that accesses the flash memory device.
The flash memory device may use a low-density parity check (LDPC) decoding technique to decode the data. The LDPC decoding technique may use a parity check matrix to decode an ECC codeword, such as by multiplying the parity check matrix and the ECC codeword to generate “decoded” data. Because the ECC codeword includes parity bits that satisfy a set of parity equations specified by the parity check matrix, one or more bit errors in the ECC codeword can be corrected using the LDPC decoding technique.
An LDPC decoding operation may be performed (or represented) using variable nodes and check nodes. The variable nodes may represent bit values of the ECC codeword, and the check nodes may represent the parity equations of the parity check matrix. Each variable node may be connected to one or more of the check nodes. The connections (or “constraints”) may represent the set of parity equations specified by the parity check matrix. If bit values of the decoded data satisfy the set of parity equations, then the decoded data is “correct” (e.g., has been successfully decoded).
If one or more bit values of the decoded data do not satisfy the set of parity equations, then one or more bit errors may be present in the ECC codeword. To illustrate, if a threshold voltage representing a particular bit of the ECC codeword is unreliable (e.g., has a value that is at or near a border between a state indicating a “0” value and a state indicating a “1” value), the correct value of the bit may be determined by verifying whether assigning a “0” value or a “1” value for the bit satisfies the set of parity equations.
If the ECC codeword includes multiple unreliable bits, decoding the ECC codeword may include “checking” each of the unreliable bits to see if a value can be determined for each unreliable bit. As an example, if a first check node is connected to multiple variable nodes associated with unreliable bits, then the parity equations corresponding to the first check node may be underdetermined. To decode the ECC codeword, a second check node may be identified connecting to a variable node associated with one of the unreliable bits. The parity equations corresponding to the second check node may be used to assign a value to the unreliable bit. After determining the value for the unreliable bit, the first check node may re-checked to determine whether the parity check equations corresponding to the first check node are no longer underdetermined or whether another check node should be identified connecting to a variable node associated with another one of the unreliable bits. Decoding the ECC codeword may include multiple such iterations to generate error-corrected data. Further, although the foregoing example uses binary values (“0” values and “1” values) for purposes of illustration, other types of values may be used in LDPC decoding. For example, a check node may pass to a variable node a log-likelihood ratio (LLR) (instead of a “0” value or a “1” value). An LLR may indicate a likelihood that a particular bit has a “0” value or a “1” value. In a two-phase message passing (TPMP) (or “belief propagation”) LDPC decoding scheme, messages may be passed between variable nodes and check nodes indicating bit reliability based on currently available information (e.g., based on information determined during a previous iteration of the decoding operation). Because of the complexity of LDPC computations, numerous techniques for decoding LDPC-encoded ECC codewords have been developed.